package problem146;

//146.LRU缓存
//https://leetcode.cn/problems/lru-cache/?envType=study-plan-v2&envId=top-interview-150

import java.util.HashMap;

class LRUCache {
    class Node {
        int key;
        int val;
        Node next;
        Node pre;
        public Node() {
        }
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    HashMap<Integer, Node> map;
    Node head;
    int size;
    int capacity;
    public LRUCache(int capacity) {
        map = new HashMap<>();
        head = new Node();
        head.next = head;
        head.pre = head;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        removeToFrist(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)) {
            Node node = map.get(key);
            removeToFrist(node);
            //更新节点的值
            node.val = value;
        }else {
            Node node = new Node(key, value);
            insertFirst(head, node);
        }
    }

    //将node节点移到链表头部
    private void removeToFrist(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        //移除node节点
        pre.next = next;
        next.pre = pre;
        //将node节点插在head后面
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
    }
    //删除尾节点
    private void delTail(Node head) {
        Node tail = head.pre;
        Node preTail = tail.pre;
        preTail.next = head;
        head.pre = preTail;

        map.remove(tail.key);
    }
    //在头部插入新节点
    private void insertFirst(Node head, Node node) {
        map.put(node.key, node);
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
        size++;
        //判断容量是否溢出
        if(size > capacity) {
            //删除尾节点
            delTail(head);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */